package buaa.leetcode.DynamicPrograming;

public class NumberOfIslands {
	public static int numIslands(char[][] grid) {
		int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        if (n == 0) return 0;
        int result = 0;
        
        for(int i = 0 ;i < m ; i++){
        	for(int j = 0; j < n ; j++){
        		if(grid[i][j] != '1') continue;
    			result++;
    			helper(grid,m,n,i,j);
        	}
          }
        return result;
    }
	private static void helper(char[][] grid,int m, int n, int i, int j){
		if (i < 0 || i >= m || j < 0 || j >= n) return;  
	        if (grid[i][j] == '1') {  
	            grid[i][j] = '#';  
	            helper(grid, m, n, i - 1, j);  
	            helper(grid, m, n, i + 1, j);  
	            helper(grid, m, n, i, j - 1);  
	            helper(grid, m, n, i, j + 1);  
	        }  

	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char[][] grid = new char[3][3];
		grid[0] = new char[]{'1','1','1'};
		grid[1] = new char[]{'0','1','0'};
		grid[2] = new char[]{'1','1','1'};
		System.out.println(numIslands(grid));
	}

}
